package Leetcode第一期;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.stream.Collectors;

/**
 * @author : K k
 * @date : 10:31 2020/9/16
 */
public class 矩阵_01_542 {
    //访问标志
    boolean[][] visited;
    //四个方向
    int[][] directions=new int[][]{{1,0},{0,1},{-1,0},{0,-1}};

    public int[][] updateMatrix(int[][] matrix) {
        int n=matrix.length;
        int m=matrix[0].length;
        Queue<int[]> queue = new LinkedList<>();

        //将非0的位置置为-1，表示未访问,0的位置入队
        for (int i=0;i<n;i++){
            for (int j=0;j<m ;j++){
                if (matrix[i][j]!=0){
                    matrix[i][j]=-1;
                }else {
                    queue.add(new int[]{i,j});
                }
            }
        }

        while (!queue.isEmpty()){
            int[] point=queue.poll();
            int x=point[0],y=point[1];
            for (int i=0;i<3;i++){
                //四个位置
                int newX=x+directions[i][0];
                int newY=y+directions[i][1];
                if (isArea(matrix,n,m,newX,newY)){
                    matrix[newX][newY]=matrix[x][y]+1; //设置了值以后则为访问位
                    queue.offer(new int[]{newX,newY});
                }
            }

        }
        return matrix;
    }

    private boolean isArea(int[][] matrix, int n, int m, int newX, int newY) {
        return newX>=0&&newX<n&&newY>=0&&newY<m&& matrix[newX][newY]==-1;
    }

    public static void main(String[] args) {
        矩阵_01_542 x=new 矩阵_01_542();
        Arrays.stream(x.updateMatrix(new int[][]{
                {0, 0, 0},
                {0, 1, 0},
                {0, 0, 0},
        })).collect(Collectors.toList()).forEach(System.out::println);
    }
}
